# -*- coding:utf-8 -*-

'''
输入一个链表，输出该链表中倒数第k个结点。
'''

'''
在一次遍历的情况下, 寻找倒数第k个结点, 可以设置两个指针
第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；
从第k步开始，第二个指针也开始从链表的头指针开始遍历。
由于两个指针的距离保持在k-1，
当第一个（走在前面的）指针到达链表的尾结点时，
第二个指针（走在后面的）指针正好是倒数第k个结点。

推广: 寻找中间节点, 两个指针一起, 第一个指针每次走两步, 第二个指针每次走一步, 
快指针指到尾部, 慢指针正好指到中间
'''

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        if head == None or k <= 0:
            return None
        
        pAHead = head
        pBehind = None
        
        for i in range(k - 1):
            if pAHead.next != None:
                pAHead = pAHead.next
            else:
                return None
        pBehind = head
        while pAHead.next != None:
            pAHead = pAHead.next
            pBehind = pBehind.next
        return pBehind

node1 = ListNode(10)
node2 = ListNode(11)
node3 = ListNode(12)
node4 = ListNode(13)
node5 = ListNode(14)
node6 = ListNode(15)
node7 = ListNode(16)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node7

S = Solution()
print(S.FindKthToTail(node1, 3).val)